package LeetCode;

import java.util.*;

public class LC_126_WordLadderII {
    public static void main(String[] args) {

    }


    public class Solution {

        public List<List<String>> findLadders(String s, String t, List<String> w) {
            List<List<String>> ans = new LinkedList<>();
            if (s == null || t == null || w == null) {
                if (s == null && t == null) ans.add(Collections.singletonList(null));
                return ans;
            }
            if (s.equals(t)) {
                ans.add(Collections.singletonList(s));
                return ans;
            }
            int sn = s.length();
            if (w.size() == 0) return ans;
            HashSet<String> nv = new HashSet<>(w);
            HashSet<String> hv = new HashSet<>();
            if (!nv.contains(t)) return ans;
            nv.add(s);
            Queue<String> q = new LinkedList<>();
            q.add(s);
            HashMap<String, List<String>> m = new HashMap<>();
            char[] cs = new char[sn];
            boolean isFind = false;
            while (!q.isEmpty()) {
                int size = q.size();
                while (size-- > 0) {
                    String n = q.poll();
                    for (int i = 0; i < sn; i++) cs[i] = n.charAt(i);
                    for (int i = 0; i < sn; i++) {
                        for (char c = 'a'; c <= 'z'; c++) {
                            cs[i] = c;
                            String nn = new String(cs);
                            if (!nv.contains(nn)) continue;
                            if (hv.add(nn)) q.add(nn);
                            if (!m.containsKey(nn)) m.put(nn, new LinkedList<>());
                            m.get(nn).add(n);
                            if (nn.equals(t)) isFind = true;
                        }
                        cs[i] = n.charAt(i);
                    }
                }
                if (isFind) break;
                nv.removeAll(hv);
                hv.clear();
            }
            find(t, s, new LinkedList<>(), m, ans);
            return ans;
        }

        private void find(String t, String s, LinkedList<String> l, HashMap<String, List<String>> m, List<List<String>> ans) {
            l.addFirst(t);
            if (t.equals(s)) {
                ans.add(new LinkedList<>(l));
            } else {
                List<String> vs = m.get(t);
                if (vs != null) {
                    for (String v : vs) {
                        find(v, s, l, m, ans);
                    }
                }
            }
            l.removeFirst();
        }

    }
}
